//
//  NumWays.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/8.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  剑指 Offer 10- II. 青蛙跳台阶问题

/*

递归两大要素：

1.终止条件；
2.递推公式。

*/

import UIKit

/*
 剑指 Offer 10- II. 青蛙跳台阶问题
 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

 示例 1：

 输入：n = 2
 输出：2
 示例 2：

 输入：n = 7
 输出：21
 提示：

 0 <= n <= 100
 
 注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/
 与裴波那契数列等价，唯一的不同在于起始数字不同
 */

class NumWays: NSObject {
    
    /*
     解题思路：
     此类求 多少种可能性 的题目一般都有 递推性质 ，即 f(n) 和 f(n-1)…f(1) 之间是有联系的。

     设跳上 n 级台阶有 f(n)f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。
        当为 1 级台阶： 已经跳过了 n-1 个台阶，此情况共有 f(n-1) 种跳法；
        当为 2 级台阶： 已经跳过了 n-2 个台阶，此情况共有 f(n-2) 种跳法。
     
     https://pic.leetcode-cn.com/108249e4d62d429f9cd6cab5bbd6afca581ee61c7d762a4c8ea0c62e08e10762-Picture13.png
     
     f(n) 为以上两种情况之和，即 f(n) = f(n-1)+f(n-2) ，以上递推性质为斐波那契数列。本题可转化为 求斐波那契数列第 n 项的值 ，与 面试题10- I. 斐波那契数列 等价，唯一的不同在于起始数字不同。
     青蛙跳台阶问题： f(0)=1, f(1)=1 , f(2)=2 ；
     斐波那契数列问题： f(0)=0, f(1)=1 , f(2)=1 。

     斐波那契数列的定义是 f(n + 1) = f(n) + f(n - 1)f(n+1)=f(n)+f(n−1) ，生成第 nn 项的做法有以下几种：

     
     递归法：
     原理： 把 f(n)f(n) 问题的计算拆分成 f(n-1)f(n−1) 和 f(n-2)f(n−2) 两个子问题的计算，并递归，以 f(0)f(0) 和 f(1)f(1) 为终止条件。
     缺点： 大量重复的递归计算，例如 f(n)f(n) 和 f(n - 1)f(n−1) 两者向下递归都需要计算 f(n - 2)f(n−2) 的值。
    
     记忆化递归法：
     原理： 在递归法的基础上，新建一个长度为 nn 的数组，用于在递归时存储 f(0)f(0) 至 f(n)f(n) 的数字值，重复遇到某数字时则直接从数组取用，避免了重复的递归计算。
     缺点： 记忆化存储的数组需要使用 O(N)O(N) 的额外空间。
     
     动态规划：
     原理： 以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)f(n+1)=f(n)+f(n−1) 为转移方程。
     
     >>>>>>>>从计算效率、空间复杂度上看，动态规划是本题的最佳解法。
     
     动态规划解析：
     状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表 斐波那契数列第 $i$ 个数字 。
     转移方程： dp[i + 1] = dp[i] + dp[i - 1] ，即对应数列定义 f(n + 1) = f(n) + f(n - 1) ；
     初始状态： dp[0] = 1, dp[1] = 1 ，即初始化前两个数字；
     返回值： dp[n] ，即斐波那契数列的第 n 个数字。
     
     空间复杂度优化：
     若新建长度为 n 的 dp 列表，则空间复杂度为 O(N) 。

     由于 dp 列表第 i 项只与第 i-1 和第 i-2 项有关，因此只需要初始化三个整形变量 sum, a, b ，利用辅助变量 sum 使 a, b 两数字交替前进即可 （具体实现见代码） 。
     因为节省了 dp 列表空间，因此空间复杂度降至 O(1) 。
     
     循环求余法：

     大数越界： 随着 nn 增大, f(n)f(n) 会超过 Int32 甚至 Int64 的取值范围，导致最终的返回值错误。

     求余运算规则： 设正整数 x, y, px,y,p ，求余符号为 \odot⊙ ，则有 (x + y) \odot p = (x \odot p + y \odot p) \odot p(x+y)⊙p=(x⊙p+y⊙p)⊙p 。
     解析： 根据以上规则，可推出 f(n) \odot p = [f(n-1) \odot p + f(n-2) \odot p] \odot pf(n)⊙p=[f(n−1)⊙p+f(n−2)⊙p]⊙p ，从而可以在循环过程中每次计算 sum = a + b \odot 1000000007sum=a+b⊙1000000007 ，此操作与最终返回前取余等价。

 
     
     题解链接： https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solution/mian-shi-ti-10-ii-qing-wa-tiao-tai-jie-wen-ti-dong/
     
     */
    
    func numWays(_ n: Int) -> Int {
        
        if n < 2 {
            return 1
        }
        
        /*
         动态规划解析 把此题想象成裴波那契数列问题
         青蛙跳台阶问题： f(0)=1, f(1)=1 , f(2)=2 ；
         斐波那契数列问题： f(0)=0, f(1)=1 , f(2)=1 。
         因此初始两个值为1
         */
        /*
         滚动数组思想
         0 1
           1 1
             1 2
               2 3
                 3 5
                   5 8
         */
        var a = 1
        var b = 1
        var sum = 0
        for _ in 0 ..< n {
            sum = (a+b)%1000000007
            a = b
            b = sum
        }
            
        return a
    }
    
    
    
    //70.爬楼梯问题  和青蛙跳台阶一样  动态规划思想  再用滚动数组来优化时间复杂度
    /*
     由于这里的 f(x) 只和 f(x−1) 与  f(x−2) 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)
           a b r
           0 0 1
 step1:      0 1 1
 step2:        1 1 2
 step3:          1 2 3
 step4:            2 3 5
 step5:              3 5 8
     */
    
    func climbStairs(_ n: Int) -> Int {
        
        var a = 0
        var b = 0
        var r = 1
        
        for _ in 1 ... n{
            a = b
            b = r
            r = a+b
        }
        return r
    }
}
